Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:

Given binary tree [3,9,20,null,null,15,7],

  1.     3
  2.    / \
  3.   9  20
  4.     /  \
  5.    15   7

return its zigzag level order traversal as:

  1. [
  2.   [3],
  3.   [20,9],
  4.   [15,7]
  5. ]

Solution:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.   public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
  12.     List<List<Integer>> res = new ArrayList<>();
  14.     if (root == null) {
  15.       return res;
  16.     }
  18.     List<Integer> list = new ArrayList<>();
  20.     Stack<TreeNode> s1 = new Stack<>();
  21.     Stack<TreeNode> s2 = new Stack<>();
  23.     boolean leftToRight = true;
  25.     s1.push(root);
  27.     while (!s1.isEmpty()) {
  28.       TreeNode node = s1.pop();
  30.       list.add(node.val);
  32.       if (leftToRight) {
  33.         if (node.left != null) {
  34.           s2.push(node.left);
  35.         }
  37.         if (node.right != null) {
  38.           s2.push(node.right);
  39.         }
  40.       } else {
  41.         if (node.right != null) {
  42.           s2.push(node.right);
  43.         }
  45.         if (node.left != null) {
  46.           s2.push(node.left);
  47.         }
  48.       }
  50.       if (s1.isEmpty()) {
  51.         leftToRight = !leftToRight;
  52.         res.add(new ArrayList<>(list));
  53.         list = new ArrayList<>();
  55.         s1 = s2;
  56.         s2 = new Stack<>();
  57.       }
  58.     }
  60.     return res;
  61.   }
  62. }